﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Misc
{
    class BinarySearchTreeNode
    {
        public int data;
        public BinarySearchTreeNode left;
        public BinarySearchTreeNode right;
        public BinarySearchTreeNode(int n)
        {
            data = n;
        }
    }
    class BST
    {
        public BinarySearchTreeNode rootNode;
        public void Add(int data)
        {
            AddNode(rootNode, data);
        }

        private BinarySearchTreeNode AddNode(BinarySearchTreeNode node, int data)
        {
            if (node == null)
            {
                node = new BinarySearchTreeNode(data);
                if(rootNode == null)
                    rootNode = node;
                return node;
            }
            if (data > node.data)
            {
                node.right = AddNode(node.right, data);
            }
            else if (data < node.data)
            {
                node.left = AddNode(node.left, data);
            }
            return node;
        }

        public void Remove(int data)
        {
            RemoveNode(rootNode, data);
        }

        private BinarySearchTreeNode RemoveNode(BinarySearchTreeNode node, int data)
        {
            if (node == null)
                return node;
            if (node.data == data)
            {
                if (node.left == null && node.right == null)
                    node = null;
                else if (node.left != null)
                {
                    BinarySearchTreeNode temp = node;
                    node = node.left;
                    BinarySearchTreeNode temp1 = node;
                    BinarySearchTreeNode temp2 = temp1;

                    if (temp2 != null)
                    {
                        while (temp2.right != null)
                        {
                            temp1 = temp2;
                            temp2 = temp2.right;
                        }
                    }

                    if (rootNode == temp)
                        rootNode = temp2;
                    temp1.right = temp2.left;
                    temp2.left = temp.left != temp2 ? temp.left : temp2.left;
                    temp2.right = temp.right;
                    node = temp2;
                }
                else if (node.right != null)
                { }
                
            }
            else if (data > node.data)
            {
                node.right = RemoveNode(node.right, data);
            }
            else if (data < node.data)
            {
                node.left = RemoveNode(node.left, data);
            }
            return node;
        }

        public static void PrintTree(BinarySearchTreeNode node)
        {
            int h = GetHeight(node);
            int rows = (h * (h + 1)) / 2;
            int cols = 2 * rows - 1;

            treeMatrix = new string[rows, cols];

            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    treeMatrix[i, j] = " ";

            Print(node, 0, (h * h + h - 2) / 2);

            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < cols; j++)
                    Console.Write(treeMatrix[i, j]);
                Console.WriteLine();
            }
        }

        private static void Print(BinarySearchTreeNode node, int row, int col)
        {
            if (node == null) return;
            int i;
            treeMatrix[row, col] = node.data.ToString();
            int height = GetHeight(node);
            for (i = 1; i < height; i++)
            {
                if (node.left != null)
                    treeMatrix[row + i, col - i] = "/";
                if (node.right != null)
                    treeMatrix[row + i, col + i] = @"\";
            }
            Print(node.left, height + row, col - i);
            Print(node.right, height + row, col + i);
        }

        private static string[,] treeMatrix;

        private static int GetHeight(BinarySearchTreeNode node)
        {
            if (node == null)
                return 0;

            else
            {
                int leftIndex = GetHeight(node.left) + 1;
                int rightIndex = GetHeight(node.right) + 1;
                return Math.Max(leftIndex, rightIndex);
            }
        } 
    }
}
